import lombok.extern.slf4j.Slf4j;

/**
 * 树形结构
 * @author zlzhangn
 */
@Slf4j
public class DataStructure_4_tree {
	//双亲表示法
	static class parent_tree{
		Node[] nodes;	//节点数组
		class Node{
			int data;	
			int parent;	//指向父节点，根节点为-1
			//int firstChild; //指向第一个孩子
			//int rightsbl;	//指向兄弟
		}
	}
	
	//孩子表示法
	static class child_tree{
		//孩子节点
		class ChildPtr{
			//int parent;	//指向双亲
			int next;	//指向下一个孩子节点
			int data;	//数据域
		}
		//表头结构
		class THead{
			int data;	//数据域
			int firstChild;	//指向该节点孩子链表的指针
		} 
		//节点数组
		THead[] nodes;
	}
	
	//孩子兄弟表示法(优势在于查找孩子；把树变为了二叉树)
	static class child_sbl_tree{
		class Node{
			//int parent;
			int firstChild;
			int rightSib;	//指向右兄弟节点
		}
		Node[] nodes;
	}
	
	//二叉树(顺序存储列表只适合完全二叉树)
	static class Bi_tree{
		String data;
		Bi_tree leftChild;
		Bi_tree rightChild;
		Bi_tree(String d){
			data = d;
		}
		Bi_tree(){}
		//输入 前序遍历序列【空节点用#表示】, 输出 二叉树
		static int counter = 0;
		static Bi_tree createBitree(String[] strArr,int start){
			Bi_tree tree = null;
			if(counter>=strArr.length || strArr[counter].equals("#")){
				return null;
			}else{
				tree = new Bi_tree(strArr[counter]);
			}
			tree.leftChild = createBitree(strArr, ++counter);
			tree.rightChild = createBitree(strArr, ++counter);
			return tree;
		}
		static Bi_tree getBItree(){
			Bi_tree biTree = new Bi_tree("a");
			biTree.leftChild = new Bi_tree("b");
			biTree.rightChild = new Bi_tree("c");
			biTree.leftChild.leftChild = new Bi_tree("d");
			biTree.leftChild.leftChild.leftChild = new Bi_tree("g");
			biTree.leftChild.leftChild.rightChild = new Bi_tree("h");
			biTree.rightChild.leftChild = new Bi_tree("e");
			biTree.rightChild.leftChild.rightChild = new Bi_tree("i");
			biTree.rightChild.rightChild = new Bi_tree("f");
			
			return biTree;
		}
		//前序遍历
		static void preOrderTraverse(Bi_tree tree){
			if(tree==null){
				return;
			}
			log.debug(tree.data);
			//遍历左树
			preOrderTraverse(tree.leftChild);
			//遍历右树
			preOrderTraverse(tree.rightChild);
		}
		//中序遍历
		static void inOrderTraverse(Bi_tree tree){
			if(tree==null){
				return;
			}
			//遍历左树
			inOrderTraverse(tree.leftChild);
			log.debug(tree.data);
			//遍历右树
			inOrderTraverse(tree.rightChild);
		}
		//后序遍历
		static void PostOrderTraverse(Bi_tree tree){
			if(tree==null){
				return;
			}
			//遍历左树
			PostOrderTraverse(tree.leftChild);
			//遍历右树
			PostOrderTraverse(tree.rightChild);
			log.debug(tree.data);
		}
	}
	
	//线索二叉树(加上了线索的二叉链表：加上了指向前驱后后继的指针)，相当于把一颗二叉树转换为了双向链表
	static class BiThrTree{
		enum pointerTag{/**指向孩子**/Link ,/**指向前驱后继**/Thread}
		pointerTag lTag;
		pointerTag rTag;
		BiThrTree leftChild;
		BiThrTree rightChild;
		String data;
		BiThrTree(String d){this.data = d;}
		//在中序遍历进行中序线索化（使用某种遍历方式将树转为线索二叉树的过程）
		static BiThrTree pre;//记录前驱
		static void inThreading(BiThrTree tree){
			if(tree==null){
				return;
			}
			//左子树线索化
			inThreading(tree.leftChild);
			if(tree.leftChild==null){
				tree.lTag = pointerTag.Thread;
				tree.leftChild = pre;
			}
			if(pre!=null && pre.rightChild==null){
				pre.rTag = pointerTag.Thread;
				pre.rightChild = tree;
			}
			pre = tree;
			//右子树线索化
			inThreading(tree.rightChild);
		}
		static BiThrTree getBItree(){
			BiThrTree biTree = new BiThrTree("a");
			biTree.leftChild = new BiThrTree("b");
			biTree.rightChild = new BiThrTree("c");
			biTree.leftChild.leftChild = new BiThrTree("d");
			biTree.leftChild.leftChild.leftChild = new BiThrTree("g");
			biTree.leftChild.leftChild.rightChild = new BiThrTree("h");
			biTree.rightChild.leftChild = new BiThrTree("e");
			biTree.rightChild.leftChild.rightChild = new BiThrTree("i");
			biTree.rightChild.rightChild = new BiThrTree("f");
			return biTree;
		}
	}
	
	public static void main(String[] args) {
		//Bi_tree.preOrderTraverse(Bi_tree.getBItree());
		//Bi_tree.inOrderTraverse(Bi_tree.getBItree());
		//Bi_tree.PostOrderTraverse(Bi_tree.getBItree());
		//Bi_tree.preOrderTraverse(Bi_tree.createBitree(new String[]{"a","b","d","e","c","#","f"}, 0));
		BiThrTree tree = BiThrTree.getBItree();
		BiThrTree.inThreading(tree);
	}
	
}
